package com.leetcode.problems075;

import com.leetcode.util.PrintUtils;

/**
 * https://leetcode-cn.com/problems/sort-colors/
 * @Date 2021/12/09 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    /**
     * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     *
     * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     *
     * 必须在不使用库的sort函数的情况下解决这个问题。
     */
    public void sortColors(int[] nums) {
        /**
         * [0,lt] 标识 RED
         * [lt+1,i) 标识 WHITE
         * [rg,nums.length - 1] 标识 BLUE
         */
        final int RED = 0;
        final int WHITE = 1;
        final int BLUE = 2;
        int lt = -1;
        int rg = nums.length;
        for (int i = 0; i < rg; ) {
            if(nums[i] == WHITE){
                i++;
            }else if(nums[i] == BLUE){
                swap(nums,i,rg - 1);
                rg--;
            }else if(nums[i] == RED){
                swap(nums,i,lt + 1);
                lt++;
                i++;
            }
        }
    }


    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int nums[] = {2,0,2,1,1,0};
        new Solution().sortColors(nums);
        PrintUtils.printArr(nums);
    }
}
